package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ65 查找两个字符串a,b中的最长公共子串  字符串, 动态规划, 双指针
 * @Date: created in 2025/1/3 星期五 16:37
 * @Modified By:
 */
public class HJ65_FindLongestCommonSubstringInTwoStrings {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.next();
            String b = in.next();

            System.out.println(longString(a, b));
        }
    }

    public static String longString(String a, String b) {
        // 保证str1是较短字符串
        String str1;
        String str2;
        if (a.length() < b.length()) {
            str1 = a;
            str2 = b;
        } else {
            str1 = b;
            str2 = a;
        }

        // dp数组长度比字符串长度多1, 0位不用
        int m = str1.length() + 1;
        int n = str2.length() + 1;

        // dp数组的定义: 表示在较短字符串str1以第i个字符结尾，
        // str2中以第j个字符结尾时的公共子串长度。
        int[][] dp = new int[m][n];

        // 公共子串的长度
        int max = 0;
        // 公共子串匹配的str1中最大的结尾下标
        int index = 0;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 状态转换, i为短字符串str1的结尾索引，j为str2的结尾索引
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 相等则在上一个公共子串长度基础上加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        // 不断更新最大公共子串的长度和匹配的下标
                        max = dp[i][j];
                        index = i;
                    }
                }
            }
        }

        // 截取最大公共子串
        return str1.substring(index - max, index);
    }
}
